/**
 * 0 onverkend, 1 muur, 2 geen muur
 */


public class Maze {
	const double SECTOR_WIDTH = 40.0;
	
	
	/**
	 * constructors
	 */
	public Maze(int size) {
		this.size = size;
		data = new char[size+1][size*2 +1];
	}
	
	public Maze(char[][] source) {
		super((source.length>source[0].length)?source.length:source[0].length);
		for(int i = 0; i<source.length; i++) {
			for(int j=0; j<source[0].length;j++) {
				data[size+1-source.length+i][j] = source[i][j];
			}
		}
	}
	
	static int xdelta(Direction dir) {
		switch(dir) {
		case EAST:
			return 1;
		case WEST:
			return -1;
		default:
			return 0;
		}
	}

	static int ydelta(Direction dir) {
		switch(dir) {
		case SOUTH:
			return -1;
		case NORTH:
			return 1;
		default:
			return 0;
		}
	}
	/**
	 * coordinates
	 */
	
	public class Coord {
		int x;
		int y;
		Coord(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
		
	/**
	 * maze implementation
	 */
	//x+ is EAST
	//y+ is NORTH
	//used to bring other Mazes in the same coordinate system
	private Coord offset = new Coord(0,0);
	private int size = 32; //12.8 meter, so the capacity increase probably won't be used
	private char data[][] = new char[size+1][2*size+1];
	private int rot = 0; //how many 90 degree rotations (clockwise) compared to how the map started
	//keep track of max/min to avoid overflows
	private int minx = 0;
	private int miny = 0;
	private int maxx = 0;
	private int maxy = 0;
	
	private int positivemodulo(int val, int mod) {
		mod = Math.abs(mod); //no negative modulo allowed
		mod = (mod==0)?1:mod; //no zero modulo either
		while(val<0) val+= mod; //increase val until we're sure it's positive
		return val%mod;
	}
	
	//resizes the matrix if necessary
	private void updateBounds(Coord calculated) {
		minx = Math.min(minx, calculated.x);
		maxx = Math.max(maxx, calculated.x);
		miny = Math.min(miny, calculated.y);
		maxy = Math.max(maxy, calculated.y);
		while((maxx-minx+1)>size || (maxy-miny+1)>size) sizeNORTH();
	}
	
	//we need to go bigger!
	private void sizeUp() {
		char temp[][] = new char[2*size+1][4*size+1];
		for(int y = 0; y< (size-positivemodulo(minx,size)); y++) {
			for(int x = 0; x<(positivemodulo(maxx,size)*2+1); x++) {
				temp[y][x] = data[y][x];
			}
		}
		for(int y = (size-positivemodulo(minx,size)); y<(size*2)+1; y++) {
			for(int x = (positivemodulo(maxx,size)*2+1); x<(size*4)+1; x++) {
				temp[y+size][x+2*size] = data[y][x];
			}
		}
		size*=2;
		data = new char[size+1][2*size+1];
		for(int y = 0; y<size+1; y++) {
			for(int x = 0; x<2*size+1; x++) {
				data[y][x] = temp[y][x];
			}
		}
	}
	
	private Coord sectorToArray(Coord local, Direction wall, boolean ownCoordinates) {
		Coord matrix = local;
		updateBounds(matrix);
		if(!ownCoordinates) {
			//apply rotation
			for(int i=0; i<rot; i++) {
				int temp = matrix.x;
				matrix.x = size-matrix.y;
				matrix.y = temp;
				wall = wall.right();
			}
			matrix.x = positivemodulo(matrix.x+offset.x,size); //apply offset and normalize
			matrix.y = positivemodulo(-matrix.y+offset.y,size); //apply offset and normalize while transforming to "y+ is SOUTH"
		} else {
			matrix.x = positivemodulo(matrix.x,size); //normalize
			matrix.y = positivemodulo(-matrix.y,size); //normalize while transforming to "y+ is SOUTH"
		}
		//calculate position in matrix
		switch(wall) {
		case NORTH:
			matrix.x = matrix.x*2 + 1;
			//matrix.y = matrix.y
			break;
		case SOUTH:
			matrix.x = matrix.x*2 + 1;
			matrix.y += 1;
			break;
		case WEST:
			matrix.x *= 2;
			matrix.y += 1;
			break;
		case EAST:
			matrix.x = matrix.x*2 + 2;
			matrix.y += 1;
			break;
		}
		return matrix;
	}
	
	/**
	 * Reads the specified wall from sector (x,y).
	 * ownCoordinates: if false, this function will use the coordinate system that was matched to another maze
	 * 				  otherwise, it will use its own local coordinates
	 */
	public char read(int x, int y, Direction wall, boolean ownCoordinates) {
		Coord temp = sectorToArray(new Coord(x,y),wall,ownCoordinates);
		return data[temp.y][temp.x];
	}

	public void write(int x, int y, Direction wall, char value, boolean ownCoordinates) {
		Coord temp = sectorToArray(new Coord(x,y),wall,ownCoordinates);
		data[temp.y][temp.x] = value;
	}
	
	/**
	 * matches the coordinate system to another maze where
	 * (localx,localy) on this maze corresponds to (targetx,targety) on the target maze
	 * returns false if the points can't be matched, true on success
	 */
	public boolean match(int localx1, int localy1, int targetx1, int targety1, int localx2, int localy2, int targetx2, int targety2) {
		//the given points are the same
		if((localx1-localx2)==0 && (localy1-localy2)==0) return false;
		//calculate differences
		int lxd = localx2 - localx1;
		int lyd = localy2 - localy1;
		int txd = targetx2 - targetx1;
		int tyd = targety2 - targety1;
		//no rotation change
		if(lxd==txd && lyd==tyd) rot = 0;
		//1 rotation
		else if(lxd==-tyd && lyd==txd) rot = 1;
		//2
		else if(lxd==-txd && lyd==-tyd) rot = 2;
		//3
		else if(lxd==tyd && lyd==-txd) rot = 3;
		//the points can't match
		else return false;
		//apply the rotation
		for(int i=0; i<rot; i++) {
			int temp = localx1;
			localx1 = -localy1;
			localy1 = temp;
		}
		//calculate the differences
		offset.x = targetx1-localx1;
		offset.y = targety1-localy1;
		return true;
	}
	
	/**
	 * matches the coordinate system to another maze where
	 * (localx,localy) on this maze corresponds to (targetx,targety) on the target maze
	 * and locald corresponds to targetd
	 * returns false if the points can't be matched, true on success
	 */
	public boolean match(int localx, int localy, int targetx, int targety, Direction locald, Direction targetd) {
		//no rotation change
		if(locald==targetd) rot = 0;
		//1 rotation
		else if(locald==targetd.left()) rot = 1;
		//2
		else if(locald==targetd.opposite()) rot = 2;
		//3
		else if(locald==targetd.right()) rot = 3;
		//the points directions
		else return false;
		//apply the rotation
		for(int i=0; i<rot; i++) {
			int temp = localx;
			localx = -localy;
			localy = temp;
		}
		//calculate the differences
		offset.x = targetx-localx;
		offset.y = targety-localy;
		return true;
	}
	
	public void draw(int posx, int posy) {
		String out = "";
		for(int y = 0; y<(size+1); y++) {
			for(int x = 0; x<(2*size+1); x++) {
				if((x==2*posx+1) && (y==size-posy+1)) {out+="*"; continue;}
				if(data[y][x]==1) {
					if(x%2!=0) out+="_";
					else out+="|";
				} else out+=" ";
			}
			out+="\n";
		}
		out+="\n\n";
		System.out.println(out);
	}
	
	public int getMaxDistance(Location location, int rotation) {
		Location start = location;
		Coord startsector = new Coord((int)Math.floor(start.x/SECTOR_WIDTH),(int)Math.floor(start.y/SECTOR_WIDTH));

		double rotRad = Math.toRadians(rotation);
		Location end = new Location(0,0);
		Coord endsector = new Coord(0,0);
		
		//work vertical
		if(Math.abs(Math.sin(rotRad))>0.7071 && Math.abs(Math.sin(rotRad)<0.996)) { //sine is larger than sqrt(2)/2 (ang>45 degrees), work vertically upwards, but don't take it too extreme (limit ~85)
			double sign = Math.signum(Math.cos(rotRad));
			endsector.x = startsector.x+(int)sign;
			end.x = (endsector.x+((sign<0.0)?1:0))*SECTOR_WIDTH;
			dist = (start.x - end.x)/Math.abs(Math.cos(rotRad));
			end.y = start.y + Math.sin(rotRad)*dist;
			endsector.y = (int)Math.floor(end.y/SECTOR_WIDTH);
			int ysign = (int)Math.signum(endsector.y-startsector.y);
			for(int ty = startsector.y; y<endsector.y; y+=ysign) {
				if(read(startsector.x,ty,(ysign<0)?Direction.SOUTH:Direction.NORTH,true)==1) {
					end.y = (ty+(ysign>0)?1:0)*SECTOR_WIDTH
					dist = (start.y - end.y)/Math.abs(Math.sin(rotRad));
					end.x = start.x + Math.cos(rotRad)*dist;
					double diffx = end.x - start.x;
					double diffy = end.y - start.y;
					return Math.sqrt(diffx*diffx + diffy*diffy);
				}
			}
			if(read(startsector.x,endsector.y,(sign<0.0)?Direction.WEST:Direction.EAST,true)==1) {
				double diffx = end.x - start.x;
				double diffy = end.y - start.y;
				return Math.sqrt(diffx*diffx + diffy*diffy);
			}
			if(sign<0.0) {
				end.x -= Math.cos(rotRad);
				end.y -= Math.sin(rotRad);
			}
			return Math.sqrt(diffx*diffx + diffy*diffy) + getMaxDistance(end,rotation)  + (sign<0.0)?1:0;
		}
		
		//work horizontal
		else { //mirror of working vertical
			double sign = Math.signum(Math.sin(rotRad));
			endsector.y = startsector.y+(int)sign;
			end.y = (endsector.y+((sign<0.0)?1:0))*SECTOR_WIDTH;
			dist = (start.y - end.y)/Math.abs(Math.sin(rotRad));
			end.x = start.x + Math.cos(rotRad)*dist;
			endsector.x = (int)Math.floor(end.x/SECTOR_WIDTH);
			int xsign = (int)Math.signum(endsector.x-startsector.x);
			for(int tx = startsector.x; x<endsector.x; x+=xsign) {
				if(read(tx,startsector.y,(xsign<0)?Direction.WEST:Direction.EAST,true)==1) {
					end.x = (tx+(xsign>0)?1:0)*SECTOR_WIDTH
					dist = (start.x - end.x)/Math.abs(Math.cos(rotRad));
					end.y = start.y + Math.sin(rotRad)*dist;
					double diffx = end.x - start.x;
					double diffy = end.y - start.y;
					return Math.sqrt(diffx*diffx + diffy*diffy);
				}
			}
			if(read(endsector.x,startsector.y,(sign<0.0)?Direction.SOUTH:Direction.NORTH,true)==1) {
				double diffx = end.x - start.x;
				double diffy = end.y - start.y;
				return Math.sqrt(diffx*diffx + diffy*diffy);
			}
			if(sign<0.0) {
				end.x -= Math.cos(rotRad);
				end.y -= Math.sin(rotRad);
			}
			return Math.sqrt(diffx*diffx + diffy*diffy) + getMaxDistance(end,rotation) + (sign<0.0)?1:0;
		}
	}
}